The simulation of dynamic processes using parametric representations is an actively pursued area. A significant advantage of parametric representation is that every point on a parametric curve or surface is determined, from only a limited number of control points. Another benefit is the existence of industry standards for parametric representations. Deformation methods that use parametric representations are usually divided into those that are related to object representation (e.g. parametric patches), and those that are independent of object representation (e.g. free-form deformation).
Objects can be parametrically represented by parametric surfaces. Initially, parametric patches were intensively used in the CAD/CAM industry. Parametric patches were later adapted to approximate and deform complex objects such as human beings (Waite, Hoch et al, Wang and Forsey). For parametric patches to model complex objects, patches are fitted to the surface points and continuity constraints must be maintained across patch boundaries. The patch surface and the object surface are not exactly the same, since parametric patches cannot easily be fitted to complex objects. Continuity constraints may limit the deformation of body movement that the parametric patches aim to simulate. Furthermore, these approaches lack high-level abstraction for shape control (Watt and Policarpo).
Free-form deformation (FFD) embeds an object in a lattice space and deforms the lattice space, thus causing the object to become deformed (Sederberg and Parry). After the initial introduction of FFD, different variations of FFD were proposed. These variations include extended free-form deformation (Coquillart), rational free-form deformation (Kalra et al, Lamousin and Waggenspack), direct free-form deformation (Hsu et al) and Dirichlet free-form deformation (Moccozet and Thalmann), etc. A similar technique is the space deformation (Bechmann). FFD requires transformation of coordinates between object space and lattice space, and transformation is required for each vertex. Furthermore, FFD is generally considered as a global and coarse deformation approach, and thus not suitable for modeling complex, subtle and local deformation, such as facial movement (Watt and Watt).
Facial animation is generally considered as a difficult area in modeling and animation, since there are many muscles on the face and they affect each other. Facial animation also has the obvious challenge of achieving desirable reality in modeling and animation. Parke and Waters surveyed the techniques of facial animation in “Computer Facial Animation”. Many surveyed methods do not use parametric representations. Singh and Fiume proposed a deformation approach that was inspired by armatures used by sculptors and was also related to axial deformation in the prior art. A wire in their approach is a curve that is used in controlling deformation of a geometric model. However, a wire only offers coarse representations, and the mechanism of muscle movement is not simulated in their method.
The methods using parametric representations in modeling and animation heretofore known suffer from additional disadvantages, which include:
(a) Static shapes are primarily parameterized. Parameterization mainly means the setup of a parametric model. For animation methods using parametric patches, the static shapes of geometric objects are approximated by parametric patches. FFD embeds an object in lattice space, when the object is in static shape.
(b) The parameterization and deformation tend to be isolated. Deformation of geometric modeling is controlled by animators. As a result, deformation may not be intuitive to users. For FFD, when an animator moves a control point in lattice space, a model embedded in the lattice may not move as the animator desires.
Traditional application of parametric curves in computer graphics includes creating surfaces, key-framing and setting motion paths, etc. Curves are also intensively used in fitting data in science and engineering.
The deformation of individual objects and the interaction of multiple objects are closely related in real life, but are traditionally approached quite differently in graphic simulation. Articulated skeletons are useful tools frequently used in object deformation, object representation, reconstruction and recognition, etc. Simulation of object interaction involves collision detection and response. Collision detection in the prior art basically relies on interference checking between simple geometric entities. Because of the lack of consistency across the literature, it is emphasized in this document that simulation of object interaction means collision detection and response, and the deformation of individual objects alone is not considered as object interaction.
The problem of collision detection has been extensively studied from different perspectives. Lin and Gottschalk, and Jiménez et al. provided recent surveys of the topic. Most methods are built on interference testing of polyhedra that represent objects. To speed up the testing, hierarchical bounding entities are used to approximate these polyhedra. Distances between these bounding entities are checked and potential interference is identified. When objects are in close proximity, spatial decomposition techniques are normally used to test exact interference.
To achieve realistic simulation, volumetric representation has advantages over conventional surface representation, primarily because volumetric data is a more natural representation for the objects and is able to represent the internal structures.
Skeletons can be built from volumetric models. Zhou and Toga proposed a voxel-coding based skeletonization method. Gagvani et al. proposed the construction of a volumetric skeleton tree using distance transform. These methods are basically not oriented towards simulation of object interaction.
Gibson proposed a linked volume representation for modeling interaction of volumetric objects, in which each element in a sampled volume is explicitly linked to its six nearest neighbors. By modifying these links, this method can simulate various object interactions, such as collision detection and response, object deformation, carving, cutting, tearing, joining, etc. The method can be considered as an improved version of the original occupancy map method. This method consumes a vast amount of memory and exhibits inertial and damping behavior. He et al. proposed a probability model of hierarchical data to take account of the lack of explicit surfaces. However, object interaction in this model was built on the conventional surface-based approach, which uses hierarchical bounding entities.
The methods heretofore known suffer from a number of disadvantages:
(a) Simulations of object deformation and object interaction are treated as distinctly different operations. In addition, simulation of collision detection and collision response also lacks a unified framework.
(b) For surface-based approach in the prior art, construction of hierarchical bounding entities is usually time-consuming. Furthermore, when objects deform, the bounding entities need to be updated.
(c) Simulation of object interaction of volumetric models either uses occupancy map method or its variations, or resorts to the conventional surface-based approach in the prior art.